package Array.easy;

/**
 * 1. 问题描述
 *      假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。
 *      可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
 *
 *      给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），
 *      和一个数n。能否在不打破种植规则的情况下种入n朵花？能则返回True，不能则返回False。
 *
 * 2. 算法分析
 *      贪心问题
 *
 *         考虑什么样的花坛可以种下花?
 *         首先f[i] = 0 这是最基本的条件，因为当前花坛有花，一定无法种植
 *         如果考虑整个花坛的中间第i个花坛,则该花坛可以种下花的条件 f[i-1] = f[i+1] = 0
 *         如果是边界的话，分两种情况：
 *             1. 左边界 即第1个花坛 种花条件 f[1] = 0
 *             2. 右边界 即最后一个花坛 种花条件 f[len-2] = 0
 *         由此我们得到如下的思路：
 *             扫描数组，如果当前花坛可以种花，将数组的这个位置设置为1，花的数量-1
 *             最后看是否还有花剩余即n是否大于0，如果是，则说明无法种下n多花，否则
 *             能
 *             实际上我们采用的是一种贪心的策略，尽可能的多种花，即隔一个种一朵花
 *             类似于这样的：[1,0,1,0,1,0]
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 种花问题 {
    public static void main(String[] args) {

    }

    /**
     * 思路简单，但是下面的代码判断太多了，可以优化，下面给出优化
     * @param flowerbed
     * @param n
     * @return
     */
    public static boolean canPlaceFlowers1(int[] flowerbed, int n) {
        int len = flowerbed.length;
        if(len == 0) {return false;}
        if(len == 1) {
            if(flowerbed[0] == 1 && n > 0) {return false;}
            return true;
        }
        for(int i = 0; i < len; i++) { // 扫描数组
            if(i == 0) {
                if(flowerbed[i] == 0 && flowerbed[i+1] == 0) {
                    n--;
                    flowerbed[i] = 1;
                }
            }
            else if(i == len-1) {
                if(flowerbed[i] == 0 && flowerbed[i-1] == 0) {
                    n--;
                    flowerbed[i] = 1;
                }
            }
            else {
                if(flowerbed[i] == 0 && flowerbed[i-1] == 0 && flowerbed[i+1] == 0) {
                    n--;
                    flowerbed[i] = 1;
                }
            }
        }
        // 因为是最大限度的将花种下，可能扫描完全之后n会变为负的，因为会有多余的花坛种下花朵
        // 所以给定的种花数量可能少于可以种植花坛的数量所以此处的判断应该是 n <= 0 而不是 n == 0
        return n <= 0;
    }

    /**
     * 利用短路逻辑简化代码
     * @param flowerbed
     * @param n
     * @return
     */
    public boolean canPlaceFlowers2(int[] flowerbed, int n) {
        if(flowerbed.length == 0) {return false;}
        for(int i = 0; i < flowerbed.length; i++) {
            // || 短路条件判断 (&&也是，如果第一个条件错误，直接返回false)
            // flowerbed[i] = 0 的前提下
            // 对于第二个条件如果当前 i == 0 整个判断就是true，后面的条件会跳过，这样就不需要将数组为1的边界单独拿出来考虑
            // 如果i == 0，则对于第三个条件 i != len - 1,说明此时整个条件判断有第三个条件的第二个决定 ，这就对应的是左边界情况
            // 同上分析可得， 中间和有边界都满足下述的条件
            if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.length-1 || flowerbed[i+1] == 0)) {
                n--;
                flowerbed[i] = 1;
            }
        }
        // 因为是最大限度的将花种下，可能扫描完全之后n会变为负的，因为会有多余的花坛种下花朵
        // 所以给定的种花数量可能少于可以种植花坛的数量所以此处的判断应该是 n <= 0 而不是 n == 0
        return n <= 0;
    }

    /**
     * 下面的代码在空间上优于我的代码
     * 我们可以分析以下，实际上上述代码在逻辑上没有什么好说的，但是其中有一个点我们必须直到
     * 如果当前花坛种下了花，则下一个花坛一定无法种植，我们只需要从下下个花坛开始判断，采用一种跳跃的方式，减少了判断次数
     * @param flowerbed
     * @param n
     * @return
     */
    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
        int len = flowerbed.length;
        int count = 0; // 记录可以种花的数量
        for(int i = 0; i < len; i++) { // 扫描整个花坛
            if(flowerbed[i] == 1) {
                i += 1; // 直接跳两个格子
            }
            else {
                // 当前第i个花坛没有花，此时我们需要分情况讨论
                if((i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.length-1 || flowerbed[i+1] == 0)) {
                    count++;
                    flowerbed[i] = 1;
                    i += 1;
                }
            }
        }
        return count >= n;
    }
}
